package com.zp.self.module.level_4_算法练习.数据结构.二叉树;

import java.util.ArrayList;
import java.util.List;

/**
 * @author By ZengPeng
 */
public class 力扣_95_不同的二叉搜索树II {
    //测试
    public static void main(String[] args) {
        List<TreeNode> treeNodes = new 力扣_95_不同的二叉搜索树II().generateTrees(4);
        System.out.println(treeNodes);
    }

    /**
    题目：给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。

     示例 1：
     输入：n = 3
     输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

     示例 2：
     输入：n = 1
     输出：[[1]]

    分析：【P 💜💜💜💜】
       1.回溯法？尾递归？：遍历1->n  让每个节点都做头节点，
                           小于head 的放在右边，大于head 的放在右边，两边生成的节点集合，再2层for循环两辆组合
            --执行用时：1 ms, 在所有 Java 提交中击败了98.23%的用户

    边界值 & 注意点：
       1.java 中需要重新重建对象，而不是只改动左右指针，这样会导致加入集合的始终是那一个对象
     **/
    public List<TreeNode> generateTrees(int n) {
        return dfs(1, n);
    }

    private List<TreeNode> dfs(int start, int end) {
        List<TreeNode> res = new ArrayList<>();
        if(start>end) return res;
        for (int i = start; i <= end; i++) {
            List<TreeNode> left=  dfs(start,i-1);
            List<TreeNode> right=  dfs(i+1,end);
            if(left.isEmpty()&&right.isEmpty()) {
                res.add(new TreeNode(i));
                return res;
            }
            if(left.isEmpty()){
                for (TreeNode aRight : right) {
                    TreeNode head = new TreeNode(i);
                    head.right = aRight;
                    res.add(head);
                }
            }else if(right.isEmpty()){
                for (TreeNode node : left) {
                    TreeNode head = new TreeNode(i);
                    head.left=node;
                    res.add(head);
                }
            }else {
                for (TreeNode aLeft : left) {
                    for (TreeNode aRight : right) {
                        TreeNode head = new TreeNode(i);
                        head.left = aLeft;
                        head.right = aRight;
                        res.add(head);
                    }
                }
            }
        }
        return res;
    }
}
